package com.lz.old.tree;

import java.util.Stack;

public class BST<E extends Comparable<E>> {
	/**
	 * 声明私有Node类
	 * @author Administrator
	 *
	 */
	private class Node {
		public E e;
		public Node left, right;

		public Node(E e, Node left, Node right) {
			this.e = e;
			this.left = null;
			this.right = null;
		}

	}
	
	private Node root;
	private int size;

	public BST() {
		this.root = null;
		this.size = 0;
	}

	public void add(E e) {
		// if (root == null) {
		// root = new Node(e, null, null);
		// } else {
		// addNode(root, e);
		// }
		root = addNode(root, e);
	}

	public Node addNode(Node node, E e) {
		// if (e.compareTo(node.e) < 0 && node.left == null) {
		// node.left = new Node(e, null, null);
		// } else if (e.compareTo(node.e) > 0 && node.right == null) {
		// node.right = new Node(e, null, null);
		// }
		if (node == null) {
			node = new Node(e, null, null);
			return node;
		}
		;
		if (e.compareTo(node.e) < 0) {
			node.left = addNode(node.left, e);

		} else if (e.compareTo(node.e) > 0) {
			node.right = addNode(node.right, e);
		}
		return node;
	}

	// 默认递归
	public void beforeGet(Node node) {
		if (node == null) {
			return;
		}
		System.out.println(node.e);
		beforeGet(node.left);
		beforeGet(node.right);
	}

	// 中序 排序
	public void innerGet(Node node) {
		if (node == null) {
			return;
		}
		innerGet(node.left);
		System.out.println(node.e);
		innerGet(node.right);
	}

	// 释放资源
	public void afterGet(Node node) {
		if (node == null) {
			return;
		}
		afterGet(node.left);
		afterGet(node.right);
		System.out.println(node.e);
	}

	/**
	 * 非递归前序
	 * 
	 * @param node
	 */
	public void beforeStack(Node node) {
		Stack<Node> stack = new Stack<>();
		stack.push(node);
		while (!stack.isEmpty()) {
			Node temp = stack.pop();
			System.out.println(temp.e);
			if (temp.right != null) {
				stack.push(temp.right);
			}
			if (temp.left != null) {

				stack.push(temp.left);
			}
		}

	}

	/**
	 * 非递归中序
	 * 
	 * @param node
	 */
	public void innerStack(Node node) {
		Stack<Node> stack = new Stack<>();
		while (node != null || !stack.empty()) {
			while (node != null) {
				stack.push(node);
				node = node.left;
			}
			if (!stack.empty()) {
				node = stack.pop();
				System.out.println(node.e + "   ");
				node = node.right;
			}
		}
	}

	/**
	 * 非递归后序
	 * 
	 * @param node
	 */
	public void afterStack(Node node) {
		Stack<Node> stack1 = new Stack<>();
		Stack<Integer> stack2 = new Stack<>();
		int i = 1;
		while (node != null || !stack1.empty()) {
			while (node != null) {
				stack1.push(node);
				stack2.push(0);
				node = node.left;
			}

			while (!stack1.empty() && stack2.peek() == i) {
				stack2.pop();
				System.out.print(stack1.pop().e + "   ");
			}

			if (!stack1.empty()) {
				stack2.pop();
				stack2.push(1);
				node = stack1.peek();
				node = node.right;
			}
		}
	}

	public static void main(String[] args) {
		
		BST<Integer> bst1 = new BST();
		Integer[] i = { 5, 2, 1, 8, 6, 3 };
		for (Integer integer : i) {
			bst1.add(integer);
		}
		System.out.println("-------------前----------");
		bst1.beforeGet(bst1.root);
		System.out.println("-----------------------");
		bst1.beforeStack(bst1.root);
		System.out.println("-------------中----------");
		bst1.innerGet(bst1.root);
		System.out.println("-----------------------");
		bst1.innerStack(bst1.root);
		System.out.println("--------------后---------");
		bst1.afterGet(bst1.root);
		System.out.println("------------------------");
		bst1.afterStack(bst1.root);

	}
}
